package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-04-08 18:56
 */
public class n_12_2 {

    public static boolean find=false;
    public static void main(String[] args)  {
    }

    public boolean hasPath (String matrix, int rows, int cols, String str) {
        int idx=0;
        char[] array = matrix.toCharArray();
        int[][] matrixs=new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrixs[i][j]=array[idx++];
            }
        }
        for (int i = 0; i < rows; i++) {
            boolean[][] isVisited=new boolean[rows][cols];
            for (int j = 0; j < cols; j++) {
                if (!find){
                    helper(matrixs,isVisited,i,j,str,0,rows,cols);
                }else {
                    return true;
                }
            }
        }
        return find;
    }


    public static void helper(int[][] matrix,boolean[][] isVisited,int m,int n, String toFind,int next,int rows,int cols){
        if (find || m>=rows||n>=cols||m<0||n<0){
            return;
        }
        char c = toFind.charAt(next);
        if (isVisited[m][n] || matrix[m][n]!=c){
            return;
        }
        if (next==toFind.length()-1){
            find=true;
            return;
        }
        isVisited[m][n]=true;
        next++;
        if (!find){
            //右
            helper(matrix,isVisited,m,n+1,toFind,next,rows,cols);
        }
        if (!find){
            //下
            helper(matrix,isVisited,m+1,n,toFind,next,rows,cols);
        }
        if (!find){
            //左
            helper(matrix,isVisited,m,n-1,toFind,next,rows,cols);
        }
        if (!find){
            //上
            helper(matrix,isVisited,m-1,n,toFind,next,rows,cols);
        }
    }
}
